<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>实现二叉搜索数</title>
</head>
<body>
    <script>
        // 创建BinarySerachTree
        // 二叉搜索数的左子树的子节点的值要小于父节点的值
        // 二叉搜索数的右子树的子节点的值要大于父节点的值
        function BinarySerachTree(){
            // 创建节点构造函数
            function Node (key){
                this.key = key
                this.left = null
                this.right = null
            }
            // 保存根属性
            this.root = null
            
            /* 二叉搜索数相关的操作方法 */
            //向树中插入数据
            BinarySerachTree.prototype.insert = function (key){
                // 根据key创建对应的节点
                var newNode = new Node(key)
                // 判断根节点是否有值
                if(this.root === null){
                    this.root = newNode
                } else {
                    this.insertNode(this.root, newNode)
                }
            }
            // 插入非根节点
            BinarySerachTree.prototype.insertNode = function (node,newNode){
                if(newNode.key < node.key){ // 向左子树插入数据 
                    if(node.left === null) { // node的左子树上没有内容就把新节点插入这个左子树
                        node.left = newNode
                    } else { // node的左子树上有内容就递归这个函数向下一个节点或者说是后面没有值的节点插入
                        this.insertNode(node.left,newNode)
                    }
                }else{ // 向右子树插入节点
                    if(node.right === null){// node的右子树上没有内容就把新节点插入这个左子树
                        node.right = newNode
                    }else{ // node的右子数上有内容
                        this.insertNode(node.right,newNode)
                    }
                }
            }

            /*
            * 遍历二叉树(先序遍历)
            *@param handler是一个函数用于遍历当前经过的节点
            */
            BinarySerachTree.prototype.preOrderTraversal = function(handler){
                this.preOrderTraversalNode(this.root,handler)
            }
            // 这里用到了递归 推出递归的方法就是遍历到了叶节点 因为叶节点后就是null
            BinarySerachTree.prototype.preOrderTraversalNode = function (node,handler){
                if(node!==null){
                    // 打印遍历当前经过的节点
                    handler(node.key)
                    // 遍历所有的左子树
                    this.preOrderTraversalNode(node.left,handler)
                    // 遍历所有的右子树
                    this.preOrderTraversalNode(node.right,handler)
                }
            }

            /*
            * 遍历二叉树(中序遍历)
            *@param handler是一个函数用于遍历当前经过的节点
            */
           BinarySerachTree.prototype.inOrderTraversal = function (handler) {
               this.inOrderTraversalNode(this.root,handler)
           }
           // 这个递归的大概意思是: 当递归到了底层3的时候因为三没有了子节点就会结束递归 并把3存起来 然后递归右节点但是3的右节点也为null
           // 所以不会进行存储 因为3完成了判断里的所有的操作5就会开始进行存储(把5存了起来)然后递归5的右节点然后把6存了起来 之后5节点结束了所有的操作
           // 7就会存起来 一直....
           BinarySerachTree.prototype.inOrderTraversalNode = function(node,handler){
               // 如果遍历到了叶节点就推出递归
               if(node !== null){
                   this.inOrderTraversalNode(node.left,handler)
                   handler(node.key)
                   this.inOrderTraversalNode(node.right,handler)
               }
           }

            /*
            * 遍历二叉树(后序遍历)
            *@param handler是一个函数用于遍历当前经过的节点
            */
           BinarySerachTree.prototype.postOrderTraversal = function(handler){
               this.postOrderTraversalNode(this.root,handler)
           }
           BinarySerachTree.prototype.postOrderTraversalNode =function(node,handler){
               if(node!==null){
                   this.postOrderTraversalNode(node.left,handler)
                   this.postOrderTraversalNode(node.right,handler)
                   handler(node.key)
               }
           }

           // 获取最大值&最小值
           BinarySerachTree.prototype.min = function (){
               var node = this.root
               while(node.left!==null){
                   node = node.left
               }
               return node.key
           }
           BinarySerachTree.prototype.max = function (){
               var node = this.root
               while(node.right!==null){
                   node = node.right
               }
               return node.key
           }

           // 搜索特定的值
           BinarySerachTree.prototype.search = function(key){
               return this.searchNode(this.root,key)
           }
           BinarySerachTree.prototype.searchNode = function (node,key){
               // 如果节点为null那么退出递归
               if(node === null){
                   return false
               }
               // 判断node节点的值和传入的key的大小
               if(node.key>key){ // 传入的较小向左边查找
                return this.searchNode(node.left,key)
               }else if(node.key<key){ // 传入的较大向右边查找
                return this.searchNode(node.right,key)
               }else{ // 相等就退出递归并把值返回出去
                return true
               }
           }

           // 删除节点
           BinarySerachTree.prototype.remove = function (key) {
               // 1. 定义临时保存的变量
               var current  = this.root // 用于存储删除的节点
               var parent = this.root // 用于存储要删除的父节点
               var isLeftChild = true // 用于判断是删除的左节点还是右节点
               // 开始查找节点
               while(current.key !==key){
                   parent = current
                   // 当查找的值小于当前节点的值就遍历节点的左边
                   if(key<current.key){
                       isLeftChild = true
                       current = current.left
                   }else{ // 当查找的值小于当前节点的值就遍历节点的左边
                    isLeftChild = false
                    current = current.right
                   }
                   // 如果current指向为null就代表找到叶节点也没找到要删除的值
                   if(current === null) return false
               }
                // 删除的节点是叶节点(没有子节点)
                if(current.left === null && current.right === null){
                    if(current === this.root){
                        this.root = null // 将根节点删除
                    }else if(isLeftChild){
                        parent.left = null // 删除的是左节点
                    }else{
                        parent.right = null
                    }
               // 删除的是含有一个子节点的节点(左节点存在右节点为null)
                }else if(current.right === null){
                    if(current=== this.root){
                        this.root = current.left
                    }else if(isLeftChild) {
                        parent.left = current.left
                    }else{
                        parent.right = current.left // 这里因为只有一个子节点右节点为null current.right = null
                    }
                } else if (current.left === null){ // 右节点存在 左节点为null
                    if(current === this.root){
                        this.root = null
                    } else if (isLeftChild){
                        parent.left = current.right
                    }else{
                        parent.right = current.right
                    }
                // 删除有两个节点的节点
                }else{
                    // 获取后继节点
                    var successor = this.getSuccessor(current)
                    // 判断是否是根节点
                    if(current === this.root){
                        this.root = successor
                    }else if(isLeftChild){
                        parent.left = successor
                    } else {
                        parent.right = successor
                    }

                    // 将删除节点的左子树赋值给successor
                    successor.left = current.left
                }
               return true
           }

           /*
           *  当我们删除的节点有两个子节点时我们必须在他的子节点里找到一个最接近他的值来代替它
           *  找到最接近删除的节点的值比它小时 我们称这个值为前驱
           *  找到最接近删除的节点的值比它大时 我们称这个值为后继
           */
          // 寻找后继的方法
          BinarySerachTree.prototype.getSuccessor =function(delNode){
              // 下面三个节点就是查找的节点路径上的最后三个节点
              var successorParent = delNode
              var successor = delNode
              var current = delNode.right // 后继需要遍历的是右节点
              // 查询节点
              while(current.right !== null){
                  successorParent = successor
                  successor = current 
                  current = current.left // 如果我们要查找后继 需要查找的是要删除的节点的右节点下的一直走左节点的那条路  当我们遇到没有左节点时就找到了
              }

              // 把替代删除节点的节点的字节点链接到替代节点的父节点上
              if(successor !=delNode.right){
                  successorParent.left = successor.right
                  successor.right = delNode.right
              }
              return successor
          }

        }
          // 测试代码
          var bst = new BinarySerachTree()
            // 插入数据
            bst.insert(11)
            bst.insert(7)
            bst.insert(15)
            bst.insert(5)
            bst.insert(3)
            bst.insert(9)
            bst.insert(8)
            bst.insert(10)
            bst.insert(13)
            bst.insert(12)
            bst.insert(14)
            bst.insert(20)
            bst.insert(18)
            bst.insert(25)
            // 测试前序遍历结果
            var resultString = ""
            bst.preOrderTraversal(function(key){
                resultString += key + ","
            })
            alert(resultString);
            // 测试中序遍历结果
            var inResultString = ""
            bst.inOrderTraversal(function(key){
                inResultString += key + ","
            })
            alert(inResultString);
            // 测试后序遍历结果
            var postResultString = ""
            bst.postOrderTraversal(function(key){
                postResultString += key + ","
            })
            alert(postResultString);
            // 获取最值
            alert(bst.min()) // 3
            alert(bst.max()) // 25
            // 查找特定的值
            alert(bst.search(10)) // true
            alert(bst.search(21)) // false
            // 测试删除
            alert(bst.remove(3));
            var removeResultString = ""
            bst.preOrderTraversal(function(key){
                removeResultString += key + ","
            });
            alert(removeResultString);
    </script>
</body>
</html>